package com.gxc.queue;

import java.util.*;

/**
 * 2XXX年，人类通过对火星的大气进行宜居改造分析，使得火星已在理论上具备人类宜居的条件；
 *
 * 由于技术原因，无法一次性将火星大气全部改造，只能通过局部处理形式；
 *
 * 假设将火星待改造的区域为row *
 * column的网格，每个网格有3个值，宜居区、可改造区、死亡区，使用YES、NO、NA代替，YES表示该网格已经完成大气改造，NO表示该网格未进行改造，后期可进行改造，NA表示死亡区，不作为判断是否改造完的宜居，无法穿过；
 *
 * 初始化下，该区域可能存在多个宜居区，并目每个宜居区能同时在每个大阳日单位向上下左右四个方向的相邻格子进行扩散，自动将4个方向相邻的真空区改造成宜居区；
 *
 * 请计算这个待改造区域的网格中，可改造区是否能全部成宜居区，如果可以，则返回改造的大阳日天教，不可以则返回-1
 *
 * 输入描述
 * 输入row * column个网格数据，每个网格值枚举值如下: YES，NO，NA；
 */
public class Mars {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> lines = new ArrayList<>();

        // 读取输入，存入列表中
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.isEmpty()) break;
            lines.add(line);
        }
        scanner.close();
        int rows = lines.size();
        int cols = lines.get(0).split(" ").length;

        String[][] grid = new String[rows][cols];
        Queue<int[]> q = new LinkedList<>();
        int toConvert = 0;  // 需要改造的区域数量

        // 初始化网格和队列
        for (int r = 0; r < rows; r++) {
            String[] row = lines.get(r).split(" ");
            for (int c = 0; c < cols; c++) {
                grid[r][c] = row[c];
                if (row[c].equals("YES")) {
                    q.add(new int[]{r, c});
                } else if (row[c].equals("NO")) {
                    toConvert++;
                }
            }
        }
        // 无初始改造点或全不可改造
        if (q.isEmpty()) {
            System.out.println(-1);
            return;
        }

        // 方向数组（上下左右）
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int days = 0;  // 改造天数

        // 广度优先搜索
        while (!q.isEmpty() && toConvert > 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] pos = q.poll();
                for (int[] dir : dirs) {
                    int newRow = pos[0] + dir[0];
                    int newCol = pos[1] + dir[1];

                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol].equals("NO")) {
                        grid[newRow][newCol] = "YES";
                        q.add(new int[]{newRow, newCol});
                        toConvert--;
                    }
                }
            }
            days++;
        }

        System.out.println(toConvert == 0 ? days : -1);
    }
}
